package codeTop.简单;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author 挚爱之夕
 * @date 2021/9/23 - 09 - 23 - 17:10
 * @Description: codeTop.简单
 * @Version: 1.0
 */
public class _006_有效括号的判断 {
    /*
    20
    给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。(先出现的左括号，其对应右括号在右括号中先出现)
     */
    public static void main(String[] args) {
        String s = "{[]}";
//        s=s.replace("[]","");
//        s=s.replace("{}","");
        boolean ans = isValid1(s);
        System.out.println(ans);
    }
    //自己写的：错误，对应左右的括号可以不相邻
    public static boolean isValid(String s) {
        for (int i = 0; i < s.length() - 1; i+=2) {
            char cur = s.charAt(i);
            if(cur=='('){
                if(s.charAt(i+1)!=')')
                    return false;
            }else if(cur=='{'){
                if(s.charAt(i+1)!='}')
                    return false;
            }else if(cur=='['){
                if(s.charAt(i+1)!=']')
                    return false;
            }else
                return false;
        }
        return true;
    }
    //栈
    public static boolean isValid1(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
    //java字符串处理
    public static boolean isValid2(String s) {
        if(s.length()%2==1){
            return false;
        }
        int length = s.length() / 2;//有这些对括号，需消除次数
        for (int i = 0; i < length; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.length() == 0;
    }
    /*
    if(s.length()%2==1){
            return false;
        }
        int length = s.length()/2;
        for(int i =0;i<length;i++){
            s.replace("{}","").replace("()","").replace("[]","");
        }
        return s.length()==0;
     */
}
